package com.itheima.leetcode.od.b.dynamicprogramming.slidingwindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringJoiner;
import java.util.stream.Collectors;

/**
 * (A卷,200分)- 最差产品奖（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * A公司准备对他下面的N个产品评选最差奖，
 * 评选的方式是首先对每个产品进行评分，然后根据评分区间计算相邻几个产品中最差的产品。
 * 评选的标准是依次找到从当前产品开始前M个产品中最差的产品，请给出最差产品的评分序列。
 * <p>
 * 输入描述
 * <p>
 * 第一行，数字M，表示评分区间的长度，取值范围是0<M<10000
 * 第二行，产品的评分序列，比如[12,3,8,6,5]，产品数量N范围是-10000 < N <10000
 * <p>
 * 输出描述
 * <p>
 * 评分区间内最差产品的评分序列
 * <p>
 * 用例
 * <p>
 * 输入	3
 * 12,3,8,6,5
 * 输出	3,3,5
 * 说明
 * 12,3,8 最差的是3
 * <p>
 * 3,8,6 最差的是3
 * <p>
 * 8,6,5 最差的是5
 * 单调队列解法（最优解法）
 */
public class WorstProductAward {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        Integer[] arr =
                Arrays.stream(sc.next().split(",")).map(Integer::parseInt).toArray(Integer[]::new);*/

        int m = 3;
        Integer[] arr =
                Arrays.stream("12,3,8,6,5".split(",")).map(Integer::parseInt).toArray(Integer[]::new);
        System.out.println(getResult(arr, m));
        System.out.println(getResult2(arr, m));
    }

    public static String getResult(Integer[] nums, int k) {
        LinkedList<Integer> queue = new LinkedList<>();
        StringJoiner sj = new StringJoiner(",");

        for (int i = 0; i < k; i++) {
            while (queue.size() > 0 && queue.getLast() > nums[i]) {
                queue.removeLast();
            }
            queue.add(nums[i]);
        }
        sj.add(queue.getFirst() + "");

        for (int i = k; i < nums.length; i++) {
            if (nums[i - k] - queue.getFirst() == 0) {
                queue.removeFirst();
            }

            while (queue.size() > 0 && queue.getLast() > nums[i]) {
                queue.removeLast();
            }
            queue.add(nums[i]);
            sj.add(queue.getFirst() + "");
        }

        return sj.toString();
    }

    /**
     * 滑动窗口-单调递增队列
     * 建议用我的写法，比较面向对象
     *
     * @param nums
     * @param k
     * @return
     */
    public static String getResult2(Integer[] nums, int k) {
        MonotonicQueue queue = new MonotonicQueue();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            // 检查队列头部元素，超过滑动窗口范围要移除
            if (k <= i && nums[i - k] == queue.peek()) { // 元素超出 滑动窗口范围 移除判断
                /*
                     移除的是上一次的滑动窗口和队列首位，因为是单调队列，超出范围的那个元素必定是当时3个当中第一个进入的，
                     因为相对来说是第一个进的，一直都在队列内，那一定是队列第一位，所以nums[i - k] == queue.peek()
                     滑动窗口的位置                最大值
                    ---------------               -----
                    [1  3  -1] -3  5  3  6  7       3
                     1 [3  -1  -3] 5  3  6  7       3
                     1  3 [-1  -3  5] 3  6  7       5
                     1  3  -1 [-3  5  3] 6  7       5
                     1  3  -1  -3 [5  3  6] 7       6
                     1  3  -1  -3  5 [3  6  7]      7
                 */
                queue.poll();
            }
            int num = nums[i];
            queue.offer(num);
            if (k - 1 <= i) {
//                System.out.println(queue.peek());
                list.add(queue.peek());
            }
        }
        return list.stream().map(String::valueOf).collect(Collectors.joining(","));
    }

    /**
     * 单调递增队列
     */
    static class MonotonicQueue {

        private LinkedList<Integer> deque = new LinkedList<>();

        public Integer peek() {
            return deque.peekFirst();
        }

        public void poll() {
            deque.pollFirst();
        }

        public void offer(int t) {
            while (!deque.isEmpty() && deque.peekLast() > t) {
                deque.pollLast();
            }
            deque.offerLast(t);
        }

        @Override
        public String toString() {
            return deque.toString();
        }
    }
}